package sword.offer;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 * 链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
 *
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class ThirtyFour {
    /**
     * 用深度优先遍历
     * 分而治之 将其化解成子问题
     * 即 找root.left和root.right的路径和等于target-root.val的路径结点
     * 基线条件：
     * 当前结点为叶子结点且sum等于target 把路径记录
     * 当前结点为空结点 说明遍历完了一个子树 且没有sum不为target
     * 难点在回溯，要将path记录的结点删除。
     * */
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> pathSum(TreeNode root, int target) {
            List<Integer> arr = new ArrayList();
            dfs(root, target, 0, arr);
            return res;
        }

        public void dfs(TreeNode root, int target, int sum, List<Integer> paths){
            if(root == null){
                return;
            }
            sum += root.val;
            paths.add(root.val);
            // 叶子结点 且 等于target
            if((root.left == null && root.right == null) && sum == target){
                // ps:这里放进去的paths的深拷贝
                res.add(new ArrayList<>(paths));
                // 移除当前的结点 回到上一层
                paths.remove(paths.size()-1);
                return;
            }
            dfs(root.left, target, sum, paths);
            dfs(root.right, target, sum, paths);
            paths.remove(paths.size()-1);
        }
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
